Solution: First Unique Character in a String

Statement#

For a given string of characters, s, your task is to find the first non-repeating character and return its index. Return $-1$ if there’s no unique character in the given string.

Constraints:

• Only lowercase english letters are accepted.
• There are no spaces in the string.

Solution#

We need to keep track of the number of occurrences of each character in the string. To achieve this, we can use a hash map to store the character as a key and its number of occurrences in the string as its corresponding value.

The algorithm proceeds through the following steps:

• Create a hash map and start a loop to traverse over the given input string.

• At each iteration, we check if the current character is present in the hash map as a key.

  • If the key exists, we increment the value corresponding to this key character by $1$.

  • Otherwise, add this new key-value pair in the hash map and set its value to $1$.

• Traverse over the input string to find the character in the hash map whose value equals $1$.

  • If it exists, return the index of this character in the string. Otherwise, return $-1$.

The slide deck below illustrates the key steps of the solution.

Time complexity#

The cost of traversing the length of the input string twice is $O(2n)$, which can be simplified to $O(n)$.

Space complexity#

The space complexity of the algorithm above is $O(1)$ because, at any time, a total of $26$ keys will be stored in the hash map. This makes it a constant space used to store the frequency of the characters’ occurrence.